public class HeapSort {
    // 堆排序
    public static void sort(Comparable[] a){
        int N = a.length;

        // for循环为最大堆的构造过程
        for (int k = (N/2-1); k >=0; k--){
            sink(a, k, N-1);
        }
        // while循环为排序过程
        while(N > 0){
            exch(a, 0, N-1);
            N--;
            sink(a, 0, N-1);
        }
    }

    // 下沉，堆的有序化
    private static void sink(Comparable[] a, int k, int n) {
        while ( 2*k+1<=n){
            int j = 2*k+1;
            if (j < n && less(a, j, j+1)) j++;
            if (!less(a, k, j)) break;
            exch(a, k, j);
            k = j;
        }
    }

    private static void exch(Comparable[] a, int i, int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    private static boolean less(Comparable[] a, int i, int j) {
        return a[i].compareTo(a[j]) < 0;
    }
}
